/**
 * 不同路径2
 * @param obstacleGrid 带障碍的数组 
 * @returns 路径数量
 */
export function uniquePathsWithObstacles (obstacleGrid: number[][]): number {
    const pathCountWithObstacles = new PathCountWithObstacles(obstacleGrid);
    return pathCountWithObstacles.getPathCount();
}

class PathCountWithObstacles {
    private pathCounts: number[][];
    private m: number;
    private n: number;
    constructor (obstacleGrid: number[][]) {
        // 行数
        this.m = obstacleGrid.length;
        // 列数
        this.n = obstacleGrid[0].length;

        // 初始化
        this.pathCounts = new Array(this.m);
        // 初始化
        let i = 0;
        while (i < this.m) {
            this.pathCounts[i] = new Array(this.n);
            i++;
        }

        // 第1行和第1列初始化为1
        for (let j = 0; j < this.pathCounts[0].length; j++) {
            this.pathCounts[0][j] = obstacleGrid[0][j] === 1 ? 0 : 1;
        }
        for (let j = 1; j < this.pathCounts.length; j++) {
            this.pathCounts[j][0] = obstacleGrid[j][0] === 1 ? 0 : 1;
        }

        this.calPathCount(this.m, this.n, obstacleGrid);
    }

    private calPathCount (m: number, n: number, obstacleGrid: number[][]) {
        for (let i = 1; i < m; i++) {
            for (let j = 1; j < n; j++) {
                this.pathCounts[i][j] = 0;
                this.pathCounts[i][j] += (obstacleGrid[i-1][j] === 1 ? 0 : this.pathCounts[i-1][j]);
                this.pathCounts[i][j] += (obstacleGrid[i][j-1] === 1 ? 0 : this.pathCounts[i][j-1]);
            }
        }
    }

    public getPathCount () {
        return this.pathCounts[this.m-1][this.n-1];
    }
}